package algorithm.sort;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/**
 * 基数排序/桶排序
 */
public class RadixSort {

    private final int[] arr = new int[10];

    @Before
    public void init() {
        for (int i = 0, j = arr.length; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * j * 1000);
        }
    }

    @Test
    public void radixSort() {
        System.out.println("排序前:" + Arrays.toString(arr));
        int max = arr[0];
        for (int i = 1, len = arr.length; i < len; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        System.out.println("最大数：" + max);
        System.out.printf("最大的数字是%d\n", max);
        //需要遍历的次数由数组最大值的位数来决定
        for (int i = 1; max / i > 0; i = i * 10) {
            int[][] buckets = new int[arr.length][10];
            //获取每一位数字(个、十、百、千位...分配到桶子里)
            for (int j = 0; j < arr.length; j++) {
                int num = (arr[j] / i) % 10;
                //将其放入桶子里
                buckets[j][num] = arr[j];
            }
            //回收桶子里的元素
            int k = 0;
            //有10个桶子
            for (int j = 0; j < 10; j++) {
                //对每个桶子里的元素进行回收
                for (int l = 0; l < arr.length; l++) {
                    //如果桶子里面有元素就回收(数据初始化会为0)
                    if (buckets[l][j] != 0) {
                        arr[k++] = buckets[l][j];
                    }
                }
            }
        }
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}